#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Miguel Silva, 6311
Estrutura de Dados e Algoritmos
Engenharia Informática 
2012/2013
Código fornecido pelo professor e, adaptado ao algoritmo mergesort
"""

from random import *
from time import clock
from math import *
from algorithms.merge_sort import MergesortClass
import matplotlib.pyplot as plt

class Protocol_Mergesort(object):
    """
    Classe Protocol Mergesort
    """
    def __init__(self, start, stop, step):
        """
        Constructor da classe Mergesort que recebe três parâmetros e,
        invoca a função que executa o algoritmo e mostra o gráfico.
        
        Argumentos:
        start -- Valor inicial para criação de lista
        stop -- Valor final para a lista
        step -- Valor de salto correspondente ao número de elementos da lista
        """
        super(Protocol_Mergesort, self).__init__()
        self.start = start
        self.stop = stop
        self.step = step
        self.run_mergesort(self.start, self.stop, self.step)
        
    def run_mergesort(self, start, stop, step):
        """
        Função que executa o algoritmo e cria as listas de acordo
        com os valore passados por argumento. Mostra ainda o gráfico com os
        valores experimentais e com os valores teóricos.

        Argumentos:
        start -- Valor inicial para criação de lista
        stop -- Valor final para a lista
        step -- Valor de salto correspondente ao número de elementos da lista
        """
        Z = [2] + range(start, stop, step)
        T = []
        M = 25
        merge = MergesortClass()
        for n in Z:
            A = [ uniform(0.0,1.0) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = clock()
                merge.merge_sort(A,1,len(A))
                t2 = clock()
                tempos.append(t2-t1)
                shuffle(A)

            media = reduce(lambda x, y: x + y, tempos) / len(tempos) # soma dos tempos / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
            
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]

        constantes = [media / (n*log(n,2)) for n, media, var in T]
        media_constantes = reduce(lambda x,y: x + y, constantes) / len(constantes)
        V=[(n*log(n,2)) * media_constantes for n in X]

        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos\nStart:{0} Stop:{1} Step:{2}'.format(start,stop,step))
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X,V, 'b^', label=u"previsão teórica")
        plt.legend()
        plt.show()
